#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <list>
#include <fstream>

#define MAXLINE 128
using namespace std ;

#define debug

struct CapAndFlow {
    int cap, flow;
    CapAndFlow():cap(-1),flow(0){};
    ~CapAndFlow(){};
};
struct node_t{
    int i; //the node number
    struct node_t* next;
    node_t():i(-1),next(NULL){};  //-1 represent there is no edge on Graph;
};

class Graph
{
    public:
        Graph();
        virtual ~Graph();
        void ReadGraph();//input file
//        void GenReGraph();//generate Regraph
        void ConReGraph();
        bool IsAugPath();//compute the augment path
        void UpdateFlow();//update the flow
        void Mincut();
        void FordFulkersonAlg();
        void ChangeReflow(int& pre, int& next);
        void mincut();


    protected:

    private:
        CapAndFlow **GraphCapFlow;  //represent the cap and flow of Graph
                                    //cap = 0 represent the edge between doesn't exist
        int **ReGraphCapFlow;       //represent the flow of Residual Graph
       // int* pnode;
        int  Nodenum;
        int  Edgenum;
        int Source;
        int Sink;
        node_t* pGraphArray;        ////represent the cap and flow of Graph
        node_t* pReGraphArray;
        list<int> AugPath;
        int bottleneck;
        int Numiterator;
        int maxflow;
        ofstream outfile;
        //vector<node_t*> GraphList;
        //vector<node_t*> ReGraphList;
};

#endif // GRAPH_H
